package org.rescue.analysis.InterDimension;

import java.util.Enumeration;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Vector;

import javax.swing.tree.DefaultMutableTreeNode;

import org.rescue.Dag.Concept;
import org.rescue.Dag.DAGNode;
import org.rescue.Dag.DirectedAcyclicGraph;

public class GreedyDAssoc {
	DirectedAcyclicGraph t;
	int totalCard;
	HashMap <Integer, Integer> bgConcepts;

	public DefaultMutableTreeNode compare (DirectedAcyclicGraph t, Concept rootConcept, 
			HashMap <Integer, Integer> bgConcepts, int totalCard, int k) {
		this.totalCard = totalCard;
		this.bgConcepts = bgConcepts;
		this.t = t;
		Enumeration<DAGNode> nodes = t.postOrder(rootConcept);
		while (nodes.hasMoreElements()) {
			DAGNode cnode = nodes.nextElement();
			//	get one created during tree formation
			Concept con = cnode.getNodeConcept();

			/* Add self in candidates tree  */
			DefaultMutableTreeNode cand = new DefaultMutableTreeNode();
			DCandidateData candData = new DCandidateData();
			candData.id = con.id;
			candData.dCard = con.dCard;
			candData.card = con.card;
			candData.isCand = false;
			candData.includeInCand = false;
			candData.setBgConcepts(((DAuxiliaryData)con.getAuxData()).cloneBGConcepts());
			cand.setUserObject(candData);			
			((DAuxiliaryData)con.getAuxData()).setCandTree(cand);

			// use cardinality set by TaxonomyReader to recursively compute parent cardinality
			con.card += con.dCard; // initialized card
			if (!cnode.isRoot()) { 
				Vector<Concept> pars = t.getParents(con);
				for (int i = 0; i < pars.size(); i++) {
					pars.elementAt(i).card += con.card;
					//System.out.println(con.id + " par card " + pars.elementAt(i).card);
				}
			}

			if (!cnode.isLeaf()) 
			{
				/* Growing phase */	
				/* Populate node's cand tree with all the candidates from all of its children;
					The candidate node being added may in turn has its own
					children which remain linked with the node. */

				for (int i = 0; i < cnode.getChildCount(); i++) 
				{
					Concept childCon = cnode.getChildAt(i).getNodeConcept();

					// since we do not remove zero-cardinality concepts 
					if (childCon.card > 0) {
						//System.out.println(childCon.id);
						DefaultMutableTreeNode childCand = ((DAuxiliaryData) childCon.getAuxData()).getCandTree(); 
						// make candtrees of all childConcepts children of candNode
						cand.add(childCand);
						DCandidateData childCandData = (DCandidateData)childCand.getUserObject();

						// can include the child in candidates
						childCandData.includeInCand = true;
						if (!childCandData.isCand) {
							candData.subCandsCount = candData.subCandsCount + childCandData.subCandsCount + 1;
						}
						else {
							candData.subCandsCount += childCandData.subCandsCount;
						}
					}
				}

				/* Merging Phase */
				/* During merging, do a postorder traversal of the candidate tree of each child and
				 * compute information loss of a meerge. 
				 * NOTE: the child cand concept is merged with the current parent cand concept
				 * if it's candidate subtree is empty and the child node is the only one left.
				 * */

				if (candData.subCandsCount <= k ) 
					continue;  // no need to merge, so continue postorder
				else 
				{
					while (candData.subCandsCount > k) 
					{
						DMinLossData minLossData, newMinLossData;
						minLossData = new DMinLossData(Double.POSITIVE_INFINITY);
						for (int j = 0; j < cand.getChildCount(); j++) 
						{ 
							System.out.println("visting under " + candData.id + " " 
									+ ((DCandidateData)((DefaultMutableTreeNode)cand.getChildAt(j)).getUserObject()).id);

							// consider merging one node
							newMinLossData = findMinLossMerge ((DefaultMutableTreeNode)cand.getChildAt(j));
							if (newMinLossData.getMinloss() < minLossData.getMinloss() ) 
							{
								minLossData = newMinLossData;
							}
						}
						System.out.println("meging " +
								((DCandidateData)minLossData.getMergeParent().getUserObject()).id
								+ " -> " +
								((DCandidateData)minLossData.getMergeChild().getUserObject()).id 
								+ "  " + minLossData.minloss);

						merge (minLossData); // merge and recomputes cardinality of candidate tree

						// if not already discounted
						if (((DCandidateData)((DefaultMutableTreeNode)minLossData.getMergeParent()).getUserObject()).id !=
							candData.id)
							candData.subCandsCount -= 1;
					}
				}
			}
			else {
				// make self a cand
				candData.subCandsCount = 1;
				candData.isCand = true;
			}
		}
		return ((DAuxiliaryData)rootConcept.getAuxData()).getCandTree();
	}

	public DMinLossData findMinLossMerge(DefaultMutableTreeNode childCand) {
		double loss;
		DefaultMutableTreeNode mergeParent;
		DefaultMutableTreeNode mergeChild;
		DMinLossData minLossData = new DMinLossData(Double.POSITIVE_INFINITY);
		Enumeration e = childCand.postorderEnumeration();

		while (e.hasMoreElements()) {
			mergeChild = (DefaultMutableTreeNode)e.nextElement();
			DCandidateData mergeChildData = (DCandidateData)mergeChild.getUserObject();

			if (mergeChildData.id == ((DCandidateData)childCand.getUserObject()).id
					&& !mergeChild.isLeaf()) { // since leaves are cands automatically
				if (mergeChildData.isCand) {
					loss = computeLoss(mergeChildData);
					minLossData.setChildCandNode(childCand);
					minLossData.setMergeChild(mergeChild);
					minLossData.setMergeParent(mergeChild);
					minLossData.setMinloss(loss);
				}
			}
			else {
				mergeParent = (DefaultMutableTreeNode) mergeChild.getParent(); 
				DCandidateData mergeParentData = (DCandidateData)mergeParent.getUserObject();
				loss = computeLoss(mergeChildData);
				//System.out.println(mergeChildData.id + " to " + mergeParentData.id + " " + loss);

				if ( loss < minLossData.getMinloss()) {
					// populate minLossData with new data
					minLossData.setChildCandNode(childCand);
					minLossData.setMergeChild(mergeChild);
					minLossData.setMergeParent(mergeParent);
					minLossData.setMinloss(loss);
				}
			}
		}	

		return minLossData; 
	}
	
	/**
	 * Do a Hash Join of the two Associated Concept lists
	 * @return
	 */
	
	public HashMap <Integer, Integer> combineBConcepts 
			(DCandidateData parentCandData, DCandidateData childCandNodeData ) {
		
		// HashMap parentAConcepts = parentNodeData.getAConcepts();
		HashMap<Integer, Integer> childBGConcepts = childCandNodeData.getBgConcepts();
		HashMap<Integer, Integer> mergedBGConcepts = parentCandData.getBgConcepts();
		
		// for each background concept
		Set<Map.Entry<Integer,Integer>> entries = childBGConcepts.entrySet();
		for(Map.Entry<Integer,Integer> entry : entries) {
			int id = entry.getKey();
			if (mergedBGConcepts.containsKey(id)) {
				int count = mergedBGConcepts.get(id);
				count += entry.getValue();
				mergedBGConcepts.put(id, count);
			}
			else {
				mergedBGConcepts.put (id, entry.getValue());
			}
		}
		return mergedBGConcepts;
	}

	public void merge (DMinLossData minLossData) {
		DefaultMutableTreeNode mergeChild = minLossData.getMergeChild();
		DefaultMutableTreeNode mergeParent = minLossData.getMergeParent();

		// (1) update minLossData.mergeParent.direcCardinality
		DCandidateData mergeParentData = (DCandidateData) mergeParent.getUserObject();
		DCandidateData mergeChildData = ((DCandidateData)mergeChild.getUserObject());

		// removing self from candidate set
		if (mergeParentData.id == mergeChildData.id) {
			mergeParentData.isCand = false;
			mergeParentData.subCandsCount -= 1;	
		}		
		else {
			mergeParentData.dCard += mergeChildData.dCard;
			HashMap <Integer, Integer>  mergedBGConcepts;
			mergedBGConcepts = combineBConcepts (mergeParentData, mergeChildData);
			mergeParentData.setBgConcepts(mergedBGConcepts);

			// (2) making children of minLossData.mergeChild children of minLossData.mergeParent
			while (mergeChild.getChildCount() > 0)
			{
				DefaultMutableTreeNode grandchildCand = (DefaultMutableTreeNode)mergeChild.getFirstChild();
				mergeParent.add(grandchildCand); // also removes grandchildCand from mergeChild.
				// due to one node one parent requirement
			}
			// (3) removing minLossData.mergeChild
			mergeChild.removeFromParent();

			if (!mergeParentData.includeInCand || mergeParentData.isCand) 
				mergeParentData.subCandsCount -= 1;
			else { // cand size not yet reduced
				mergeParentData.isCand = true;
			}
		}
	}
	/**
	 * 
	 * @param childcard
	 * @param parentcard
	 * @param distance is the distance between the two merged concepts
	 * @return
	 */

	public double log2(double d) {
		return Math.log(d)/Math.log(2.0);
	}

	public double computeLoss(DCandidateData mergeChildCandData) {
		double loss = 0.0;
		// smoothing		
		HashMap<Integer,Integer> bgc = mergeChildCandData.bgConcepts;
		// no of concepts in q but not in p
		int smoothAdd = bgConcepts.size() - bgc.size();
		int smoothTotal = totalCard + smoothAdd;
		//TODO: find out how to smooth for concepts in p but not in q 
		int smoothedFGCDCard = mergeChildCandData.dCard+smoothAdd;
		
		// for each background concept
		Set<Map.Entry<Integer,Integer>> entries = bgConcepts.entrySet();
		for(Map.Entry<Integer,Integer> entry : entries) {
		    int bgcId = entry.getKey();
		    int bgcTotal = entry.getValue();
		    
		    int bgFgCount;
			if (bgc.containsKey(bgcId) && bgc.get(bgcId) > 0) {
				bgFgCount = bgc.get(bgcId);	
			}
			else {
				bgFgCount = 1; // smooth
			}
		    
		    double p = (double) bgFgCount/smoothedFGCDCard;		    
		    
		    // TODO: smooth q, but not added to smoothAdd
		    double q;
		    if (bgcTotal - bgFgCount == 0) {
		    	q = (double)1 /(smoothTotal-smoothedFGCDCard);
		    }
		    else {
		    	q = (double) (bgcTotal - bgFgCount)/(smoothTotal-smoothedFGCDCard);
		    }
		  //  System.out.println("p = " + p + " q = " + q);
		    
		 //	System.out.println("bgcTotal= " + bgcTotal + " bgFgCount= " + bgFgCount +
		  //			" smoothedFGCDCard=" +smoothedFGCDCard);
		    
			loss += p * log2 (p/q);
		}
		System.out.println("consider " + mergeChildCandData.id + " with loss: " + loss);
		return loss;
	}
}
